package com.leetcode.algorithm.y22.m06;

/**
 * 69. x 的平方根
 * 
 * https://leetcode.cn/problems/sqrtx/
 * 
 * @author jie.deng
 *
 */
public class Question0069Solution02 {

	/**
	 * 69. x 的平方根
	 * 
	 * 实现 int sqrt(int x) 函数。
	 * 
	 * 计算并返回 x 的平方根，其中 x 是非负整数。
	 * 
	 * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
	 * 
	 * 示例 1:
	 * 
	 * 输入: 4 输出: 2 示例 2:
	 * 
	 * 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
	 * 
	 * @param x
	 * @return
	 */
	public int mySqrt(int x) {
		if (x == 0 || x == 1) {
			return x;
		}
		int left = 1;
		int right = x;
		int mid = left + ((right - left) >> 1);
		while (!(mid <= x / mid && (mid + 1) > x / (mid + 1))) {
			if (mid < x / mid) {
				left = mid;
				mid = left + ((right - left) >> 1);
			} else {
				right = mid;
				mid = left + ((right - left) >> 1);
			}
		}
		return mid;
	}

}
